{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Oracle Definition ##"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This implements the oracle $D |z\\rangle |k\\rangle = |z \\oplus x_k \\rangle |k\\rangle$ used in the Grover\n",
    "search algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "[\"ApplyDatabaseOracle\"]",
      "text/html": [
       "<ul><li>ApplyDatabaseOracle</li></ul>"
      ],
      "text/plain": [
       "ApplyDatabaseOracle"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "operation ApplyDatabaseOracle(\n",
    "    markedElement : Int,\n",
    "    markedQubit: Qubit,\n",
    "    databaseRegister: Qubit[]\n",
    ") : Unit is Adj + Ctl {\n",
    "    (ControlledOnInt(markedElement, X))(databaseRegister, markedQubit);\n",
    "\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "{\"name\":\"Microsoft.Quantum.Canon.ControlledOnInt\",\"kind\":3,\"source\":\"/home/jovyan/.nuget/packages/microsoft.quantum.standard/0.11.2004.2825/lib/netstandard2.1/Microsoft.Quantum.Standard.dll\",\"documentation\":\" # Summary\\n Returns a unitary operator that applies an oracle on the target register if the control register state corresponds to a specified positive integer.\\n\\n # Input\\n ## numberState\\n Positive integer.\\n ## oracle\\n Unitary operator.\\n\\n # Output\\n A unitary operator that applies `oracle` on the target register if the control register state corresponds to the number state `numberState`.\"}",
      "text/html": [
       "<h4><i class=\"fa fas fa-terminal\"></i> Microsoft.Quantum.Canon.ControlledOnInt <a href=\"/home/jovyan/.nuget/packages/microsoft.quantum.standard/0.11.2004.2825/lib/netstandard2.1/Microsoft.Quantum.Standard.dll\"><i class=\"fa fas fa-code\"></i></a></h4><h1>Summary</h1>\n",
       "<p>Returns a unitary operator that applies an oracle on the target register if the control register state corresponds to a specified positive integer.</p>\n",
       "<h1>Input</h1>\n",
       "<h2>numberState</h2>\n",
       "<p>Positive integer.</p>\n",
       "<h2>oracle</h2>\n",
       "<p>Unitary operator.</p>\n",
       "<h1>Output</h1>\n",
       "<p>A unitary operator that applies <code>oracle</code> on the target register if the control register state corresponds to the number state <code>numberState</code>.</p>\n"
      ],
      "text/plain": [
       "Microsoft.Quantum.Canon.ControlledOnInt"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ControlledOnInt?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## State Preparation ##"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This implements an oracle $DU$ that prepares the start state\n",
    "$DU |0\\rangle|0\\rangle = 1 / \\sqrt{N} |1\\rangle|\\text{marked}\\rangle + \\sqrt{N - 1} / \\sqrt{N} |0\\rangle|\\text{unmarked}\\rangle$ where $N = 2^n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "[\"PrepareDatabaseRegister\"]",
      "text/html": [
       "<ul><li>PrepareDatabaseRegister</li></ul>"
      ],
      "text/plain": [
       "PrepareDatabaseRegister"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation PrepareDatabaseRegister(\n",
    "    markedElement : Int,\n",
    "    idxMarkedQubit: Int,\n",
    "    startQubits: Qubit[]\n",
    ") : Unit is Adj + Ctl {\n",
    "    let flagQubit = startQubits[idxMarkedQubit];\n",
    "    let databaseRegister = Exclude([idxMarkedQubit], startQubits);\n",
    "\n",
    "    // Apply 𝑈.\n",
    "    ApplyToEachCA(H, databaseRegister);\n",
    "\n",
    "    // Apply 𝐷.\n",
    "    ApplyDatabaseOracle(markedElement, flagQubit, databaseRegister);\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, we wrap our state preparation in a *user-defined type* to indicate that it is a state preparation oracle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "[\"GroverStatePrepOracle\"]",
      "text/html": [
       "<ul><li>GroverStatePrepOracle</li></ul>"
      ],
      "text/plain": [
       "GroverStatePrepOracle"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "open Microsoft.Quantum.Oracles;\n",
    "\n",
    "function GroverStatePrepOracle(markedElement : Int) : StateOracle {\n",
    "    return StateOracle(PrepareDatabaseRegister(markedElement, _, _));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grover's Algorithm ##"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "[\"GroverSearch\"]",
      "text/html": [
       "<ul><li>GroverSearch</li></ul>"
      ],
      "text/plain": [
       "GroverSearch"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "open Microsoft.Quantum.AmplitudeAmplification;\n",
    "\n",
    "function GroverSearch(\n",
    "    markedElement: Int,\n",
    "    nIterations: Int,\n",
    "    idxMarkedQubit: Int\n",
    ") : (Qubit[] => Unit is Adj + Ctl) {\n",
    "\n",
    "    return StandardAmplitudeAmplification(nIterations, GroverStatePrepOracle(markedElement), idxMarkedQubit);\n",
    "\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "[\"ApplyQuantumSearch\"]",
      "text/html": [
       "<ul><li>ApplyQuantumSearch</li></ul>"
      ],
      "text/plain": [
       "ApplyQuantumSearch"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "open Microsoft.Quantum.Measurement;\n",
    "open Microsoft.Quantum.Arrays;\n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "operation ApplyQuantumSearch() : (Result, Int) {\n",
    "\n",
    "    let nIterations = 6;\n",
    "    let nDatabaseQubits = 6;\n",
    "    let markedElement = 3;\n",
    "    \n",
    "    using ((markedQubit, databaseRegister) = (Qubit(), Qubit[nDatabaseQubits])) {\n",
    "\n",
    "        // Implement the quantum search algorithm.\n",
    "        (GroverSearch(markedElement, nIterations, 0))([markedQubit] + databaseRegister);\n",
    "\n",
    "        // Measure the marked qubit. On success, this should be One.\n",
    "        let resultSuccess = MResetZ(markedQubit);\n",
    "\n",
    "        // Measure the state of the database register post-selected on\n",
    "        // the state of the marked qubit.\n",
    "        let resultElement = ForEach(MResetZ, databaseRegister);\n",
    "        let numberElement = ResultArrayAsInt(resultElement);\n",
    "\n",
    "        // Returns the measurement results of the algorithm.\n",
    "        return (resultSuccess, numberElement);\n",
    "\n",
    "    }\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "{\"@type\":\"@tuple\",\"Item1\":1,\"Item2\":3}",
      "text/plain": [
       "(One, 3)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%simulate ApplyQuantumSearch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Epilogue ##"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "{\"rows\":[{\"@type\":\"@tuple\",\"Item1\":\"iqsharp\",\"Item2\":\"0.11.2004.2825\"},{\"@type\":\"@tuple\",\"Item1\":\"Jupyter Core\",\"Item2\":\"1.3.52077.0\"},{\"@type\":\"@tuple\",\"Item1\":\".NET Runtime\",\"Item2\":\".NETCoreApp,Version=v3.1\"}]}",
      "text/html": [
       "<table><thead><tr><th>Component</th><th>Version</th></tr></thead><tbody><tr><td>iqsharp</td><td>0.11.2004.2825</td></tr><tr><td>Jupyter Core</td><td>1.3.52077.0</td></tr><tr><td>.NET Runtime</td><td>.NETCoreApp,Version=v3.1</td></tr></tbody></table>"
      ],
      "text/plain": [
       "Component    Version\r\n",
       "------------ ------------------------\r\n",
       "iqsharp      0.11.2004.2825\r\n",
       "Jupyter Core 1.3.52077.0\r\n",
       ".NET Runtime .NETCoreApp,Version=v3.1\r\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%version"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
